#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>

/*
	表达式求值问题，例如输入表达式 4+(3-1)-6/2+5*7，
	结果是 38。提示：可以使用二叉树以及它的遍历。
*/

typedef struct node
{
	float data;
	struct node *up;
	struct node *down;
} Stack;

Stack *create(int n)
{
	int i;
	Stack *bottom = (Stack *)malloc(sizeof(Stack));
	bottom->down = NULL;
	Stack *top = bottom;
	for (i = 0; i < n; i++)
	{
		top->up = (Stack *)malloc(sizeof(Stack));
		top->up->down = top;
		top = top->up;
	}
	top->up = NULL;
	return bottom->up;
};

void destroy(Stack *p)
{
	Stack *up = p;
	while (up->up != NULL)
	{
		up = up->up;
	}
	while (up->down != NULL)
	{
		up = up->down;
		free(up->up);
	}
	free(up);
}

int push(Stack **top, float data)
{
	if ((*top)->up != NULL)
	{
		*top = (*top)->up;
		(*top)->data = data;
		return 0;
	}
	else
	{
		return -1;
	}
}

float pop(Stack **top)
{
	assert((*top)->down != NULL);
	float data = (*top)->data;
	(*top) = (*top)->down;
	return data;
}

int main()
{
	char InfixExpression[100];
	printf("Enter an arithmetic expression: ");
	scanf("%s", InfixExpression);
	int length = strlen(InfixExpression);
	char SuffixExpression[length];
	Stack *stack = create(length);
	char *p1, *p2;
	p1 = InfixExpression;
	p2 = SuffixExpression;
	while (*p1 != '\0')
	{
		if (isdigit(*p1))
		{
			*p2 = *p1;
			p1++;
			p2++;
		}
		else if (*p1 == '(')
		{
			push(&stack, *p1);
			p1++;
		}
		else if (*p1 == ')')
		{
			while (stack->data != '(')
			{
				*p2 = pop(&stack);
				p2++;
			}
			pop(&stack);
			p1++;
		}
		else
		{
			if (stack->data == '(')
			{
				push(&stack, *p1);
				p1++;
			}
			else if ((*p1 == '*' || *p1 == '/') &&
					 (stack->data == '+' || stack->data == '-'))
			{
				push(&stack, *p1);
				p1++;
			}
			else
			{
				*p2 = pop(&stack);
				p2++;
			}
		}
	}
	while (stack->down != NULL)
	{
		*p2 = pop(&stack);
		p2++;
	}
	p1 = SuffixExpression;
	float n1, n2;
	char character[1];
	while (*p1 != '\0')
	{
		if (isdigit(*p1))
		{
			character[0] = *p1;
			push(&stack, atof(character));
		}
		else
		{
			n2 = pop(&stack);
			n1 = pop(&stack);
			if (*p1 == '+')
			{
				push(&stack, n1 + n2);
			}
			if (*p1 == '-')
			{
				push(&stack, n1 - n2);
			}
			if (*p1 == '*')
			{
				push(&stack, n1 * n2);
			}
			if (*p1 == '/')
			{
				push(&stack, n1 / n2);
			}
		}
		p1++;
	}
	printf("result = %f \n", pop(&stack));
	return 0;
}
